/**
 * @param {number[][]} grid
 * @return {number}
 */
function shortestBridge(grid) {

  const m = grid.length
  const n = grid[0].length

  //深度遍历寻找岛1,//首先获取岛屿1的开始深度遍历坐标
  const stack = [];
  let flag = false;
  for (let x = 0; x < m; x++) {
    for (let y = 0; y < n; y++) {
      if (grid[x][y] === 1) {
        stack.push([x, y]);
        flag = true;
        break;
      }
    }
    if(flag) break;
  }

  //标记岛屿1为2
  while (stack.length) {
    const [x, y] = stack.pop();
    grid[x][y] = 2
    const coordinatesList = findAllRound(x, y)
    const len = coordinatesList.length;
    //遍历将连在一起的1设置为2
    for (let i = 0; i < len; i++) {
      const [_x, _y] = coordinatesList[i];
      if (grid[_x][_y] === 1) {
        grid[_x][_y] = 2
        stack.push([_x, _y])
      }
    }
  }

  //查找四周坐标
  function findAllRound(x, y) {
    const coordinatesList = []
    //上
    if (x - 1 >= 0) coordinatesList.push([x - 1, y])
    //下
    if (x + 1 < m) coordinatesList.push([x + 1, y])
    //左
    if (y - 1 >= 0) coordinatesList.push([x, y - 1])
    //右
    if (y + 1 < n) coordinatesList.push([x, y + 1])

    return coordinatesList
  }

  //广度遍历，获取岛屿1到岛屿2的距离
  const queue = []
  for (let x = 0; x < m; x++) {
    for (let y = 0; y < n; y++) {
      //此时的岛屿1数字1已经被标记为了2
      if (grid[x][y] === 2) {
        queue.push({
          pos: [x, y],
          dis: 0
        })
      }
    }
  }

  while (queue.length) {
    const {
      pos,
      dis
    } = queue.shift();
    const [x, y] = pos

    const nbs = findAllRound(x, y)
    const len = nbs.length
    for (let i = 0; i < len; i++) {
      const [_x, _y] = nbs[i]
      //说明是岛屿1的边界.扩大岛屿1.
      if (grid[_x][_y] === 0) {
        grid[_x][_y] = 2
        queue.push({
          pos: [_x, _y],
          dis: dis + 1
        })
        //说明已经找到了岛屿2
      } else if (grid[_x][_y] === 1) {
        return dis;
      }
    }
  }

  return 0
};
let A = [
  [0, 1],
  [1, 0]
];
console.log(shortestBridge(A));
A = [
  [0, 1, 0],
  [0, 0, 0],
  [0, 0, 1]
];
console.log(shortestBridge(A));
A = [
  [1, 1, 1, 1, 1],
  [1, 0, 0, 0, 1],
  [1, 0, 1, 0, 1],
  [1, 0, 0, 0, 1],
  [1, 1, 1, 1, 1]
];
console.log(shortestBridge(A));
A = [
  [0, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 1, 0, 0, 0],
  [0, 0, 0, 0, 1, 1, 0, 0],
  [0, 0, 0, 1, 1, 0, 1, 0],
  [0, 0, 0, 0, 0, 1, 1, 0],
  [0, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 0]
];
console.log(shortestBridge(A));
A = [
  [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
  [1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
  [0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
  [1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0],
  [1, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0],
  [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0],
  [1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
  [1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
  [1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0],
  [1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0],
  [1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0],
  [1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0],
  [1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0],
  [1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0],
  [1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0],
  [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0]
];
console.log(shortestBridge(A));
